{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Distinct Binary Strings After Applying Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countDistinctStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #应用操作后不同二进制字符串的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<strong>二进制&nbsp;</strong>字符串 <code>s</code> 和一个正整数 <code>k</code>。</p>\n",
    "\n",
    "<p>你可以对字符串应用以下操作&nbsp;<strong>任意&nbsp;</strong>次数:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从 <code>s</code> 中选择任何大小为 <code>k</code> 的子字符串，将其所有字符&nbsp;<strong>翻转</strong>，即将所有 <code>1</code>&nbsp;都变成 <code>0</code>，所有 <code>0</code>&nbsp;都变成 <code>1</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em>您可以获得的&nbsp;<strong>不同&nbsp;</strong>字符串的数量。</em>因为答案可能太大，所以对 <code>10<sup>9</sup> + 7</code>&nbsp;<strong>取模&nbsp;</strong>后返回。</p>\n",
    "\n",
    "<p><b>注意</b>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二进制字符串是&nbsp;<strong>仅由&nbsp;</strong>字符 <code>0</code> 和 <code>1</code> 组成的字符串。</li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">子字符串是字符串的连续部分。</p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"1001\", k = 3\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 我们可以获得以下字符串:\n",
    "- 对字符串不应用任何操作将得到 s = \"1001\"。\n",
    "- 对从下标 0 开始的子字符串应用一个操作，得到 s = \"<u><strong>011</strong></u>1\"。\n",
    "- 对从下标 1 开始的子字符串应用一个操作，得到 s = \"1<u><strong>110</strong></u>\"。\n",
    "- 对从下标 0 和 1 开始的两个子字符串都应用一个操作，得到 s = \"<u><strong>0000</strong></u>\"。\n",
    "可以证明，我们不能获得任何其他字符串，所以答案是 4。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"10110\", k = 5\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 我们可以获得以下字符串:\n",
    "- 对字符串不执行任何操作，将得到 s = \"10110\"。\n",
    "- 对整个字符串应用一个操作将得到 s = \"01001\"。\n",
    "可以证明，我们不能获得任何其他字符串，所以答案是 2。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;是&nbsp;<code>0</code> 或&nbsp;<code>1</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-distinct-binary-strings-after-applying-operations](https://leetcode.cn/problems/number-of-distinct-binary-strings-after-applying-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-distinct-binary-strings-after-applying-operations](https://leetcode.cn/problems/number-of-distinct-binary-strings-after-applying-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1001\"\\n3', '\"10110\"\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2,len(s) - k + 1,10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        p=len(s)-k+1\n",
    "        return 2**p%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        return 2**(n-k+1)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 数学\n",
    "    # 考虑s中长度为k的子串有len(s) - k + 1个,每个子串有翻转与不翻转两个状态\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2, len(s) - k + 1, 10 ** 9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2, len(s) - k + 1, 10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "# from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "def pow_mod(a, k, p):\n",
    "    ans = 1\n",
    "    pow_val = a % p # a的2^0次方，数值就是a\n",
    "    while k != 0:\n",
    "        if k & 1 != 0:\n",
    "            ans = (ans * pow_val) % p\n",
    "        pow_val = (pow_val ** 2) % p\n",
    "        k >>= 1\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        x = len(s)-k+1\n",
    "        return pow_mod(2, x, MOD)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        # 脑筋急转弯\n",
    "        # 由于每一段区间只有翻转和不翻转\n",
    "        # 可以翻转的长度为 (n - k) + 1\n",
    "        # 所以可能性为 2**p\n",
    "        return pow(2, (len(s)-k+1), int(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2,len(s)-k+1,1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2,len(s) - k + 1,10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinctStrings(self, s: str, k: int) -> int:\n",
    "        return pow(2, len(s) - k + 1, 10 ** 9 + 7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
